package com.ww.springboot.boot.algorithm.leetcode1;

import com.ww.springboot.boot.utils.ObjectUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 描述：四数之和
 *
 * @author 🧑 ‍wanwei
 * @since 2023-07-22 17:21
 */
public class DE18 {

    public static void main(String[] args) {

        int[] nums = {2,2,2,2,2};
        int target = 8;

        List<List<Integer>> lists = fourSum(nums, target);
        System.out.println(lists);
    }


    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        List<String> numRecordList = new ArrayList<>();
        int total = 0;

        run(1, "", nums, numRecordList, total, target, 0);
        run(1, "" + nums[0], nums, numRecordList, nums[0], target, 1);

        numRecordList.forEach(record -> {
            String[] split = record.split(",");
            list.add(Arrays.stream(split).map(s -> Integer.valueOf(s)).collect(Collectors.toList()));
        });

        return list;
    }

    private static void run(int x, String numRecord, int[] nums, List<String> numRecordList, int total, int target, int num) {
        if (num == 4) {
            if (total == target) {
                numRecordList.add(numRecord);
            }
            return;
        }
        if (x >= nums.length) {
            return;
        }
        if (nums.length - x < 4 - num) {
            return;
        }
        if (num != 4) {
            run(x + 1, ObjectUtil.isEmpty(numRecord) ? "" + nums[x] : numRecord + "," + nums[x], nums, numRecordList, total + nums[x], target, num + 1);
            run(x + 1, numRecord, nums, numRecordList, total, target, num);
        }
    }
}

